【LeetCode 74】Search a 2D Matrix 搜索二维矩阵

问题描述:

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

说明：解集不能包含重复的子集。

示例1:

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

Solution:

Solution: 二维矩阵从左到右、从上到下均为升序，可以用两次二分查找，先定位到元素所在行，再在本行查找元素即可。

Code:

class solution {
    public static  boolean searchMatrix (int[][] matrix, int target) {
        int n = matrix.length;
        if(n==0)
            return false;
        int m = matrix[0].length;
        if(m==0)
            return false;
        int i = 0, j = n - 1, midColumn = 0;
        while (i <= j) {
            midColumn = (i + j) / 2;
            if (matrix[midColumn][0] <= target && target <= matrix[midColumn][m - 1])
                break;
            if(target<matrix[midColumn][0])
                j=midColumn-1;
            else
                i=midColumn+1;
        }
        if (i > j)
            return false;
        int p = 0, q = m - 1, midRow = 0;
        while (p <= q) {
            midRow = (p + q) / 2;
            if (matrix[midColumn][midRow] == target)
                return true;
            else if(matrix[midColumn][midRow]<target)
                p=midRow+1;
            else
                q=midRow-1;
        }
        return false;
    }
}